package leetcode.sort;

import java.util.Arrays;

/**
 * refer：https://blog.csdn.net/nrsc272420199/article/details/82587933
 * @author : zx
 * @version V1.0
 */
public class QuickSort  {

    public static<V extends Comparable> void sort(int low, int high, V[] array) {
        if (low < high){
            int i = findIndex(low, high, array);
            // 二分
            sort(i+1,high, array);
            sort(low, i-1, array);
        }
    }

    /**
     * 查找中间点
     * @param low 起点
     * @param high 终点
     * @param array 原数组
     * @param <V> 泛型
     * @return 中间点位置
     */
    private static<V extends Comparable> int findIndex(int low, int high, V[] array){
        // 记录起点值，留替换中间点
        V tmp = array[low];
        while (low < high){
            // 尾部开始遍历直到找到第一个小于tmp的值且头尾不相交
            while (low < high && array[high].compareTo(tmp) >= 0){
                high--;
            }
            array[low] = array[high];
            // 头部开始遍历直到找到第一个小于tmp的值且头尾不相交，否则进行交换
            while (low < high && array[low].compareTo(tmp) <= 0){
                low++;
            }
            array[high] = array[low];
        }
        // 替换为中心节点值
        array[low] = tmp;
        // 返回中间节点位置
        return low;
    }

    /**
     * 对字符串数组按照最后一个字节进行快排
     * @param s
     * @return
     */
    private static String[] sort(String[] s, int low, int high){
        if (low < high){
            int start = low;
            int stop = high;
            String tmp = s[low];
            char[] ctmp = tmp.toCharArray();
            while (low < high){
                char[] clow = s[low].toCharArray();
                char[] chigh = s[high].toCharArray();
                while (chigh[chigh.length-1] > ctmp[ctmp.length-1] && low < high){
                    high--;
                    chigh = s[high].toCharArray();
                }
                s[low] = s[high];
                while (clow[clow.length-1] < ctmp[ctmp.length-1] && low < high){
                    low++;
                    clow = s[low].toCharArray();
                }
                s[high] = s[low];
            }
            s[low] = tmp;
            sort(s, start, low-1);
            sort(s, low+1, stop);
            return s;
        }else {
            return s;
        }
    }

    public static void main(String args[]){
        Integer[] a = {3,4,2,1};
        sort(0, a.length-1, a);
        System.out.println(Arrays.toString(a));
    }
}
